package base

func QuickSort(arr []int) {
	if len(arr) > 2 {
		var left, right = 0, len(arr) - 1
		quickSort1(arr, left, right)
	}
}
func quickSort1(array []int, left, right int) {
	if left >= right {
		return
	}
	index := partition(array, left, right)
	go quickSort1(array, left, index-1)
	go quickSort1(array, index+1, right)
}

func partition(array []int, left, right int) int {
	baseNum := array[left]
	for left < right {
		for array[right] >= baseNum && right > left {
			right--
		}
		array[left] = array[right]
		for array[left] <= baseNum && right > left {
			left++
		}
		array[right] = array[left]
	}
	array[right] = baseNum
	return right
}
